class Solution {
    // 定义一个备忘录
    int[][] memo;
    public int uniquePaths(int m, int n) {
        memo = new int[m + 1][n + 1];
        return dfs(m, n);
    }
    public int dfs(int i, int j){
        // 递归开始前，查一下备忘录
        if(memo[i][j] != 0){
            return memo[i][j];
        }
        if(i == 0 || j == 0){
            // 每次返回前将值存在备忘录里面
            memo[i][j] = 0;
            return 0;
        }
        if(i == 1 && j == 1){
            // 每次返回前将值存在备忘录里面
            memo[i][j] = 0;
            return 1;
        }
        // 每次返回前将值存在备忘录里面
        memo[i][j] = dfs(i - 1, j) + dfs(i , j - 1);
        return memo[i][j];
    }
}